Hashing
Hashing, bir anahtar-değer ikilisine dayalı olarak verileri depolamak ve aramak için kullanılan bir yöntemdir. Bu yöntemde, anahtar değerleri özel bir matematiksel işleme tabi tutularak, bu işlem sonucunda elde edilen değere göre bir dizi indeksleri belirlenir. Bu dizideki her bir indeks, bir kova (bucket) olarak adlandırılır ve her bir kova, bir değer depolayabilir.
Hashing'in avantajı, anahtar-değer ikililerini çok hızlı bir şekilde depolayabilmesi ve arayabilmesidir.
Örneğin, bir telefon defteri uygulaması düşünelim. Bu uygulama, her bir kişi için bir isim ve telefon numarası ikilisini depolamak istiyor. Hashing kullanarak, kişilerin isimleri özel bir matematiksel işleme tabi tutulur ve bu işlemin sonucunda elde edilen değere göre bir dizi indeksler belirlenir. Bu dizideki her bir indeks, bir kova (bucket) olarak adlandırılır ve her bir kova, bir kişinin isim-telefon numarası ikilisini depolayabilir.
Hashing'in dezavantajı, çakışma (collision) adı verilen durumlarda ortaya çıkabilir. Çakışma, farklı anahtar değerlerinin aynı indekse (kova) atanması durumudur. Bu durumda, farklı anahtar-değer ikililerinin aynı kovada saklanması gerekebilir ve bu, veri yapısının performansını düşürebilir.
Separate Chaining (Çakışma Yönetimi)
Separate Chaining, hashing yöntemiyle verilerin depolanmasında kullanılan bir tekniktir. Bu teknikte, her bir kova (bucket) bir bağlı liste (linked list) olarak düşünülür. Aynı indekse (kova) atanmış olan anahtar-değer ikilileri, aynı bağlı listeye eklenir.
Separate Chaining'in avantajı, çakışmaların yönetimi konusunda çok etkili olmasıdır.
Örneğin, bir telefon defteri uygulaması düşünelim. Bu uygulama, her bir kişi için bir isim ve telefon numarası ikilisini depolamak istiyor. Separate Chaining kullanarak, kişilerin isimleri özel bir matematiksel işleme tabi tutulur ve bu işlemin sonucunda elde edilen değere göre bir dizi indeksler belirlenir. Bu dizideki her bir indeks, bir kova (bucket) olarak adlandırılır ve her bir kova, bir bağlı liste olarak düşünülür. Eğer farklı anahtar değerleri aynı indekse atanırsa, bu anahtar değerleri aynı bağlı liste içinde depolanır.
Separate Chaining'in dezavantajı, bellek kullanımıdır. Eğer bir bağlı liste çok uzun olursa, bu bağlı listeyi depolamak için gereken bellek miktarı da artacaktır.
Open Addressing (Lineer Probing ve Quadratic Probing)
Quadratic Probing yönteminde, bir çakışma oluştuğunda aynı indekse atanmış olan anahtar-değer ikilisi, birinci boş kova bulunana kadar bir artan katsayı (1, 2, 3, vb.) kullanılarak hash tablosu içinde sırayla yerleştirilir.
Örneğin, yine bir telefon defteri uygulaması düşünelim. Quadratic Probing yöntemi kullanarak, kişilerin isimleri özel bir matematiksel işleme tabi tutulur ve bu işlemin sonucunda elde edilen değere göre bir dizi indeksler belirlenir. Eğer farklı anahtar değerleri aynı indekse atanırsa, bu anahtar değerleri birinci boş kova bulunana kadar, bir artan katsayı kullanılarak sırayla yerleştirilir.
Open Addressing yöntemleri, Separate Chaining'e göre daha az bellek kullanır ve arama işlemlerinde daha az harici bellek erişimi gerektirir. Ancak, daha fazla çarpışma oluşma olasılığı vardır ve bu da performansı olumsuz yönde etkileyebilir.
Lineer Probing Insert İşlemi (C Kodu)
Aşağıda, Linear Probing yöntemi kullanarak bir hash tablosuna yeni bir anahtar-değer çifti ekleyen C kodu örneği verilmiştir:
#define SIZE 10 // Hash tablosunun boyutu
int hash(int key) {
return key % SIZE; // Basit bir hash fonksiyonu
}
void insert(int hash_table[], int key, int value) {
int index = hash(key);
int i = 0;
while (hash_table[(index + i) % SIZE] != -1) { // Boş kova bulana kadar döngüyü sürdür
i++;
if (i == SIZE) { // Hash tablosu dolu
printf("Hash table is full.\n");
return;
}
}
hash_table[(index + i) % SIZE] = value; // Boş kova bulundu, değeri yerleştir
}
Bu örnekte,
SIZEadında bir define sabiti tanımlanmıştır.
hash()fonksiyonu, basit bir mod alma işlemi ile bir anahtarın hash tablosu içindeki indeksini belirlemektedir. — Hash Fonksiyonu
insert() fonksiyonu, hash tablosuna yeni bir anahtar-değer çifti eklemek için kullanılır. İlk olarak, anahtarın hash değeri hesaplanır ve bu değer bir indeks olarak kullanılır. Daha sonra, hash tablosunda bu indekste boş bir kova bulana kadar döngü içinde gezinilir. Boş bir kova bulunduğunda, değer bu kovaya yerleştirilir. Eğer hash tablosu dolu ise, ekleme işlemi yapılamaz ve bir hata mesajı yazdırılır.
Lineer Probing Search İşlemi C Kodu
Aşağıda, Linear Probing yöntemi kullanarak bir hash tablosunda bir anahtarı arayan C kodu örneği verilmiştir:
#define SIZE 10 // Hash tablosunun boyutu
int hash(int key) {
return key % SIZE; // Basit bir hash fonksiyonu
}
int search(int hash_table[], int key) {
int index = hash(key);
int i = 0;
while (hash_table[(index + i) % SIZE] != -1) { // Boş kova bulana kadar döngüyü sürdür
if (hash_table[(index + i) % SIZE] == key) { // Anahtar bulundu
return (index + i) % SIZE;
}
i++;
if (i == SIZE) { // Hash tablosunun tamamı gezildi, anahtar yok
return -1;
}
}
return -1; // Anahtar yok
}
Bu örnekte de
SIZEadında bir define sabiti tanımlanmıştır.
hash()fonksiyonu, basit bir mod alma işlemi ile bir anahtarın hash tablosu içindeki indeksini belirlemektedir. — Anahtar Arama
search() fonksiyonu, hash tablosunda bir anahtarı aramak için kullanılır. İlk olarak, anahtarın hash değeri hesaplanır ve bu değer bir indeks olarak kullanılır. Daha sonra, hash tablosunda bu indeksten başlayarak bir döngü ile gezinilir. Anahtar bulunana kadar, bir sonraki kovaya geçilir. Eğer anahtar bulunursa, bu kovanın indeksi döndürülür. Eğer hash tablosunun tamamı gezilirse ve anahtar bulunamazsa, -1 değeri döndürülür.
Quadratic Probing C Kodu
Quadratic Probing, Open Addressing yöntemlerinden biridir ve Lineer Probing'in dezavantajlarını gidermek için kullanılır. Aşağıda Quadratic Probing yöntemi kullanarak bir hash tablosuna veri eklemek için C kodu örneği verilmiştir:
#define SIZE 10 // Hash tablosunun boyutu
#define EMPTY -1 // Boş kova değeri
int hash(int key) {
return key % SIZE; // Basit bir hash fonksiyonu
}
void insert(int hash_table[], int key) {
int index = hash(key);
int i = 0;
while (hash_table[(index + i*i) % SIZE] != EMPTY) { // Boş kova bulana kadar döngüyü sürdür
i++;
if (i == SIZE) { // Hash tablosunun tamamı gezildi, ekleme yapılamaz
printf("Hash tablosu dolu!\n");
return;
}
}
hash_table[(index + i*i) % SIZE] = key; // Anahtar ekle
}
Bu örnekte de
SIZEadında bir define sabiti tanımlanmıştır.
hash()fonksiyonu, basit bir mod alma işlemi ile bir anahtarın hash tablosu içindeki indeksini belirlemektedir. — Veriyi Ekleme
insert() fonksiyonu, hash tablosuna bir anahtar eklemek için kullanılır. İlk olarak, anahtarın hash değeri hesaplanır ve bu değer bir indeks olarak kullanılır. Daha sonra, hash tablosunda bu indeksten başlayarak bir döngü ile gezinilir. Eğer boş bir kova bulunursa, anahtar bu kovaya eklenir. Eğer boş kova bulunamazsa, bir sonraki kovaya geçmek yerine Quadratic Probing yöntemi kullanılarak boş bir kova aranır. i değişkeni, karelerinde artarak bir sonraki kovaya geçişi sağlar. Eğer hash tablosunun tamamı gezilirse ve boş bir kova bulunamazsa, "Hash tablosu dolu!" mesajı ekrana yazılır.